package ADD_project;

public class MatrixChain {
    /*
    int[] p表示各矩阵的行列数，p[i]表示第i各矩阵的行数和第i+1个矩阵的列数
    int n:表示连乘的矩阵个数
    int[][] m表示最优值，其中m[i][j]表示从第i个矩阵乘到第j个矩阵所需的最少乘法次数
    int[][] s表示最优断开位置的数组，其中s[i][j]表示从第i个矩阵乘到第j个矩阵时
    在s[i][j]个矩阵断开
    * */
    public static void matrixChain(int[] p,int n,int[][] m,int[][] s){
        for (int i=1;i<=n;i++){
            m[i][i]=0;//一个矩阵时，不必划分
        }

        for (int r=2;r<=n;r++){
            for (int i=1;i<=n-r+1;i++){
                int j=i+r-1;//链长为r的连乘矩阵，从第i个到第j个，功r个
                m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
                s[i][j]=i;//记住划分位置

                for (int k=i+1;k<j;k++){
                    int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if (t<m[i][j]){
                        m[i][j]=t;
                        s[i][j]=k;
                    }
                }
            }
        }
    }
}
